package com.zp.self.module.level_4_算法练习.算法.二分查找;

/**
 * @author By ZengPeng
 */
public class 力扣_74_搜索二维矩阵 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_74_搜索二维矩阵().searchMatrix(new int[][]{{1,3,5,7},{10,11,16,20},{23,30,34,60}},3));
        System.out.println(new 力扣_74_搜索二维矩阵().searchMatrix(new int[][]{{1,3,5,7},{10,11,16,20},{23,30,34,60}},10));
        System.out.println(new 力扣_74_搜索二维矩阵().searchMatrix(new int[][]{{1,3,5,7},{10,11,16,20},{23,30,34,60}},20));
        System.out.println(new 力扣_74_搜索二维矩阵().searchMatrix(new int[][]{{1,3,5,7},{10,11,16,20},{23,30,34,60}},23));
        System.out.println(new 力扣_74_搜索二维矩阵().searchMatrix(new int[][]{{1,3,5,7},{10,11,16,20},{23,30,34,60}},60));
        System.out.println(new 力扣_74_搜索二维矩阵().searchMatrix(new int[][]{{1,3,5,7},{10,11,16,20},{23,30,34,60}},13));
        System.out.println(new 力扣_74_搜索二维矩阵().searchMatrix(new int[][]{{1,3,5,7}},1));
        System.out.println(new 力扣_74_搜索二维矩阵().searchMatrix(new int[][]{{1,3,5,7}},20));
        System.out.println(new 力扣_74_搜索二维矩阵().searchMatrix(new int[][]{{1,3,5,7}},-1));
    }

    /**
    题目：编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
     每行中的整数从左到右按升序排列。
     每行的第一个整数大于前一行的最后一个整数。
      
     示例 1：
     输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
     输出：true

     示例 2：
     输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
     输出：false

    分析：【P 💙💚💜】
       1.二分行，二分列
       2.拉成一维数组：通过right = m*n-1 ,
                       然后算出mid,将mid转换为多少行多少列
            --执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

    边界值 & 注意点：
       1.
     **/
    public boolean searchMatrix(int[][] matrix, int target) {
        int row=matrix.length,clou=matrix[0].length,left=0,right= row *clou-1,mid;
        while (left<=right){
            mid=left+(right-left)/2;
            int midValue =matrix[mid/clou][mid%clou];
            if(target>midValue){
                left=mid+1;
            }else if(target<midValue)
                right=mid-1;
            else
                return  true;
        }
        return  false;

        //1.二分行，二分列
        /*int lrow = 0,rrow =matrix.length-1;
        while (lrow<=rrow){
            int mid = lrow+(rrow-lrow)/2;
            if(matrix[mid][0]>target){
                rrow= mid-1;
            }else if(matrix[mid][0]<target){
                lrow=mid+1;
            }else return true;
        }
        if(rrow<0)return false;
        int[] matrix1 = matrix[rrow];
        int left = 0,right =matrix1.length-1;
        while (left<=right){
            int mid = left+(right-left)/2;
            if(matrix1[mid]>target){
                right = mid-1;
            }else if(matrix1[mid]<target){
                left = mid+1;
            }else return  true;
        }
        return false;*/
    }
}
